package link;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
 * 如果是，返回 true ；否则，返回 false 。
 */
public class leetCode234_isPalindrome {
    public static void main(String[] args) {
        leetCode234_isPalindrome leetCode234_isPalindrome = new leetCode234_isPalindrome();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);
        leetCode234_isPalindrome.isPalindrome(head);
    }

    public boolean isPalindrome(ListNode head) {
        if(head == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        // fast != null 表示是奇数
        if(fast != null){
            slow = slow.next;
        }
        ListNode reverse = reverse(slow);
        ListNode left = head;
        while (reverse != null){
            if(left.val != reverse.val){
                return false;
            }
            reverse = reverse.next;
            left = left.next;
        }
        return true;

    }

    private ListNode reverse(ListNode head){
        if(head == null) return null;
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }



    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
